﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
//题目力扣138题：复制带随机指针的链表
//题目：给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
//
//构造这个链表的  深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
//
//例如，如果原链表中有 X 和 Y 两个节点，其中 X.random-- > Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random-- > y 。
//
//返回复制链表的头节点。
//
//用一个由 n 个节点组成的链表来表示输入 / 输出中的链表。每个节点用一个 [val, random_index] 表示：
//
//val：一个表示 Node.val 的整数。
//random_index：随机指针指向的节点索引（范围从 0 到 n - 1）；如果不指向任何节点，则为  null 。
//你的代码 只 接受原链表的头节点 head 作为传入参数。

  struct Node 
  {
    int val;
     struct Node *next;
     struct Node *random;
  };
 

struct Node* copyRandomList(struct Node* head)
{
    //首先我们要判断这个链表是否为空
    if (!head)
        return NULL;
    struct Node* cur = head;
    while (cur)
    {
        struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));//创建一个新节点
        newnode->val = cur->val;
        newnode->random = NULL;//这里我们只是复制链表里面的值，但是并不复制random指针
        //并将其与原链表链接
        newnode->next = cur->next;
        cur->next = newnode;
        cur = cur->next->next;//这里cur的next指针已经指向了复制节点所以要前进两步才会
        //让cur进入原链表的下一个
    }//这个循环也就完成了原链表的每一个节点的复制并且将其和原链表链接起来
    cur = head;//让cur重新指向头节点
    //下面我们就要开始为复制节点的random赋值了
    //因为现在的复制链表也在原链表内部所以不会出现指向问题
    while (cur)
    {
        if (cur->random)//如果原链表某个节点的random不为空那么我们就要为这个
            //节点的复制节点的random赋值
        {
            cur->next->random = cur->random->next;
        }
        cur = cur->next->next;//因为一个next只是让cur去到复制节点而已
    }
    //完成random之后我们就来到了最后一步分离复制链表和原链表
    struct Node* newhead = head->next;//这是我们最后要返回的复制节点的头节点
    cur = head;
    while (cur)
    {
        struct Node* p2 = cur->next;
        cur->next = p2->next;//这里的p2是复制节点复制节点指向的自然是原链表的下一个节点
        if (p2->next)
            p2->next = cur->next->next;//这里的cur->next已经被修改了这里的cur->next指向的是原链表的第二个
        //节点而这个原链表的第二个节点的下一个节点自然就是复制链表的第二个节点
        cur = cur->next;//为下一次分离做准备
        //这里的判断条件来源就是当复制链表的下一个节点已经指向空了代表这已经到最后了不需要在改变复制链表的next了
    }
    return newhead;
}
//题目二：力扣160题相交链表
struct ListNode
{
    int val;
    struct Node* next;
    struct Node* random;
};
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
    //先确定这两个链表是否相交
    struct ListNode* curA = headA;
    int lenA = 0;
    struct ListNode* curB = headB;
    int lenB = 0;
    while (curA)
    {
        curA = curA->next;
        lenA++;
    }
    while (curB)
    {
        curB = curB->next;
        lenB++;
    }
    if (curA != curB)
        return NULL;//证明这两个链表没有节点
    struct ListNode* longlist = headA;
    struct ListNode* shortlist = headB;
    int gbs = abs(lenA - lenB);//算出差值
    if (lenB > lenA)
    {
        longlist = headB;
        shortlist = headA;
    } //这种写法就能够减少重复代码的使用
    while (gbs--)
    {
        longlist = longlist->next;
    }
    while (longlist != shortlist)
    {
        shortlist = shortlist->next;
        longlist = longlist->next;
    }
    return shortlist;
}